/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  if (s.length === 0) return 0
  // dp[0] = 0，一个字符不可能组成有效括号
  const dp = new Array(s.length).fill(0)
  for (let i = 1; i < s.length; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        dp[i] = 2
        if (i - 2 >= 0) {
          dp[i] += dp[i - 2]
        }
      } else {
        if (i - dp[i - 1] - 1 >= 0) {
          if (s[i - dp[i - 1] - 1] === ')') dp[i] = 0
          else {
            dp[i] = dp[i - 1] + 2
            if (i - dp[i - 1] - 2 >= 0) {
              dp[i] += dp[i - dp[i - 1] - 2]
            }
          }
        }
      }
    }
  }
  return Math.max(...dp)
};
// 括号匹配的方法
var longestValidParentheses = (s) => {
  const ans = 0
  // 括号匹配可以用栈，记录长度栈存储的为下标
  const stack = [ -1 ]
  for(let i = 0; i < s.length; i++) {
    if(s[i] == '(') { // 左括号直接入栈
      stack.push(i)
    } else {
      stack.pop()
      if(stack.length) { // 栈不空
        let tempAns = i - stack[stack.length - 1]
        ans = Math.max(tempAns, ans)
      } else {
        stack.push(i) // 栈空，当前右括号下标入栈充当标志位
      }
    }
  }
  return ans
}